package lsj;

import java.util.*;

public class ShuDu {
    private Integer[] one = {1,2,3,4,5,6,7,8,9};
    //数独
    private Integer[][] shudu = new Integer[9][9];
    //记录对角线3个小九宫格
    private Integer[][] tempshudu = new Integer[9][9];
    private int answerNumber=0;
    /**
     * 获取一个随机的数独模板
     * @return
     * @throws Exception
     */
    private Integer[][] getShuDuByDiagonal() throws Exception {
        initShuDu();
        return shudu;
    }

    /**
     * 生成+校验
     * @return
     */
    private void initShuDu() throws Exception {
        //全部初始化0
        initSet();
        //初始化对角
        initDiagonal();
        //初始化其他
        initOther(0,0);
    }
    /**
     * 初始化对角线(1、5、9九宫格)
     * @return
     */
    private void initDiagonal(){
        for(int num=0;num<3;num++){
            List<Integer> list = Arrays.asList(one);
            //数组随机打乱
            Collections.shuffle(list);
            int key=0;
            for(int x=num*3;x<num*3+3;x++){
                for(int y=num*3;y<num*3+3;y++){
                    shudu[x][y]=list.get(key);
                    tempshudu[x][y]=list.get(key);
                    key++;
                }
            }
        }
    }
    /**
     * 初始化（根据对角线初始化）
     * @return
     */
    private boolean initOther(int row,int col){
        //已经到最后一行最后一列
        if(row==8&&col==9){
            return true;
        }
        if(col==9){
            col=0;
            row=row+1;
        }
        if(tempshudu[row][col]!=0){
            return initOther(row,col+1);
        }else{
            for (int num = 1; num <= 9; num++) {
                //判断给i行j列放1-9中的任意一个数是否能满足规则
                if(num==10){
                    //不能满足，回溯
                    return false;
                }
                if (check(row, col, num)) {
                    //将该值赋给该空格，然后进入下一个空格
                    shudu[row][col] = num;
                    boolean flg=initOther(row, col + 1);
                    //初始化该空格
                    if(flg==false){
                        //回溯当前格子
                        shudu[row][col] = 0;
                    }else{
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public int getAnswerNumber(Integer[][] shudu){
        this.shudu=shudu;
        this.tempshudu = shudu;
        getAnswerNumber(0,0);
        return answerNumber;
    }
    /**
     * 求解
     * @return
     */
    private void getAnswerNumber(int row,int col){
        //已经到最后一行最后一列
        if(row==8&&col==9){
            answerNumber++;
            printArray();
            return;
        }
        if(col==9){
            col=0;
            row=row+1;
        }
        if(tempshudu[row][col]!=0){
            getAnswerNumber(row,col+1);
        }else{
            for (int num = 1; num <= 9; num++) {
                //判断给i行j列放1-9中的任意一个数是否能满足规则
                if(num==10){
                    //不能满足，回溯
                    return ;
                }
                if (check(row, col, num)) {
                    //将该值赋给该空格，然后进入下一个空格
                    shudu[row][col] = num;
                    getAnswerNumber(row, col + 1);
                    //初始化该空格
                    shudu[row][col] = 0;
                }
            }
        }
    }
    /**
     * 打印矩阵
     */
    public void printArray() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(shudu[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    /**
     * 判断给某行某列赋值是否符合规则
     *
     * @param row    被赋值的行号
     * @param line   被赋值的列号
     * @param number 赋的值
     * @return
     */
    private boolean check(int row, int line, int number) {
        //判断该行该列是否有重复数字
        for (int i = 0; i < 9; i++) {
            if (shudu[row][i] == number || shudu[i][line] == number) {
                return false;
            }
        }
        //判断小九宫格是否有重复
        int tempRow = row / 3;
        int tempLine = line / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (shudu[tempRow * 3 + i][tempLine * 3 + j] == number) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 初始化0
     */
    private void initSet(){
       for(int row=0;row<9;row++){
           for(int col=0;col<9;col++) {
               shudu[row][col]=0;
               tempshudu[row][col]=0;
           }
       }
    }
    /**
     * 校验生成的数独是否正确
     * @param shudu
     * @return
     */
    public boolean CheckShuDu(Integer[][] shudu){
        //记录列
        List<Map<Integer,Boolean>> RowList =  new ArrayList<>();
        //记录列
        List<Map<Integer,Boolean>> ColList =  new ArrayList<>();
        //记录小九宫格
        List<Map<Integer,Boolean>> GridList =  new ArrayList<>();
        for(int key=0;key<9;key++){
            RowList.add(new HashMap<Integer,Boolean>());
            ColList.add(new HashMap<Integer,Boolean>());
            GridList.add(new HashMap<Integer,Boolean>());
        }
        //循环每一行校验
        for(int rowKey=0; rowKey<9; rowKey++){
            for(int colKey=0; colKey<9; colKey++){
                if(shudu[rowKey][colKey]<=0||shudu[rowKey][colKey]>9){
                    return false;
                }
                /**
                 * 如果行记录不存在，增加
                 * 如果行已经存在该数字，不符合数独规则，返回false
                 */
                Map<Integer,Boolean> rowMap = RowList.get(rowKey);
                if(rowMap.get(shudu[rowKey][colKey])==null){
                    rowMap.put(shudu[rowKey][colKey],true);
                }else{
                    return false;
                }
                /**
                 * 如果列记录不存在，增加
                 * 如果列已经存在该数字，不符合数独规则，返回false
                 */
                Map<Integer,Boolean> colMap = ColList.get(colKey);
                if(colMap.get(shudu[rowKey][colKey])==null){
                    colMap.put(shudu[rowKey][colKey],true);
                }else{
                    return false;
                }
                /**
                 * 如果小九宫格记录不存在，增加
                 * 如果小九宫格已经存在该数字，不符合数独规则，返回false
                 */
                Map<Integer,Boolean> gridMap = GridList.get(colKey/3+(rowKey/3)*3);
                if(gridMap.get(shudu[rowKey][colKey])==null){
                    gridMap.put(shudu[rowKey][colKey],true);
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 打印数独数组
     */
    public void printShuDu(){
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++");
        for(int rowKey=0; rowKey<9; rowKey++){
            if(rowKey%3==0){
                System.out.println("\t");
            }
            for(int colKey=0; colKey<9; colKey++){
                if(colKey%3==0){
                    System.out.print("\t");
                }
                System.out.print(shudu[rowKey][colKey]+"\t");
            }
            System.out.println();
        }
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++");
    }
    /**
     * 打印数独数组
     */
    public void printShuDu(Integer[][]shudu){
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++");
        for(int rowKey=0; rowKey<9; rowKey++){
            if(rowKey%3==0){
                System.out.println("\t");
            }
            for(int colKey=0; colKey<9; colKey++){
                if(colKey%3==0){
                    System.out.print("\t");
                }
                System.out.print(shudu[rowKey][colKey]+"\t");
            }
            System.out.println();
        }
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++");
    }



}
